package leetcode.code1584;

import java.util.Arrays;

import leetcode.IDebug;
import leetcode.helper.HelpDebug;

public class Solution implements IDebug {

	public int minCostConnectPoints(int[][] points) {
		int len = points.length;
		int edgeSize = (len * (len - 1)) >> 1;
		int[][] edges = new int[edgeSize][3];
		int p = 0;
		for (int i = 0; i < len; i++) {
			int[] arri = points[i];
			for (int j = i + 1; j < len; j++) {
				int[] arrj = points[j];
				edges[p][0] = i;
				edges[p][1] = j;
				edges[p][2] = Math.abs(arri[0] - arrj[0]) + Math.abs(arri[1] - arrj[1]);
				p++;
			}
		}
		Arrays.sort(edges, (a, b) -> a[2] - b[2]);
		UnionFind uf = new UnionFind(len);
		int ans = 0;
		int size = 0;
		for (int i = 0; i < edgeSize && size != len; i++) {
			int[] edge = edges[i];
			int point1 = edge[0], point2 = edge[1], value = edge[2];
			if (!uf.isSameSet(point1, point2)) {
				uf.union(point1, point2);
				ans += value;
				size++;
			}
		}
		return ans;
	}

	class UnionFind {
		int[] roots;
		int[] sizes;
		int[] stack;

		public UnionFind(int n) {
			roots = new int[n];
			sizes = new int[n];
			for (int i = 0; i < n; i++) {
				roots[i] = i;
				sizes[i] = 1;
			}
			stack = new int[n];
		}

		public int findRoot(int id) {
			int root = 0;
			int p = 0;
			while ((root = roots[id]) != id) {
				stack[p++] = id;
				id = root;
			}
			while (p > 0) {
				roots[stack[--p]] = root;
			}
			return root;
		}

		public boolean isSameSet(int id1, int id2) {
			return findRoot(id1) == findRoot(id2);
		}

		public void union(int id1, int id2) {
			int p1 = this.findRoot(id1);
			int p2 = this.findRoot(id2);
			if (p1 != p2) {
				int size1 = this.sizes[p1];
				int size2 = this.sizes[p2];
				if (size1 < size2) {
					this.roots[p1] = p2;
					this.sizes[p2] = size1 + size2;
					this.sizes[p1] = 0;
				} else {
					this.roots[p2] = p1;
					this.sizes[p1] = size1 + size2;
					this.sizes[p2] = 0;
				}
			}
		}
	}

	@Override
	public void debug1() {
		HelpDebug.compare(20, this.minCostConnectPoints(HelpDebug.str2array1("[[0,0],[2,2],[3,10],[5,2],[7,0]]")));

	}

	@Override
	public void debug2() {
		HelpDebug.compare(18, this.minCostConnectPoints(HelpDebug.str2array1("[[3,12],[-2,5],[-4,1]]")));
	}

	@Override
	public void debug3() {
		HelpDebug.compare(4000000, this.minCostConnectPoints(HelpDebug.str2array1("[[-1000000,-1000000],[1000000,1000000]]")));
	}

	@Override
	public void debug4() {
		HelpDebug.compare(0, this.minCostConnectPoints(HelpDebug.str2array1("[[0,0]]")));
	}

	public static void main(String[] args) {
		Solution so = new Solution();
		so.debug1();
		so.debug2();
		so.debug3();
		so.debug4();

	}

}
